Sistemi Operativi I A.A. 1998/99 - Docente: Giuliana Franceschinis | |
| |
(1) |
A che cosa serve un sistema operativo ? Suggerimento: vi sono più risposte possibili, corrispondenti a diversi punti di vista, per esempio quello dell'utente (che vorrà un sistema facile da usare e con tempi di risposta brevi), o quello di chi fa pagare gli utenti per l'utilizzo delle risorse di calcolo (il cui obiettivo sarà un utilizzo intenso delle risorse). |
(2) | Qual è il principale vantaggio della multiprogrammazione? Quali sono i problemi (in termini di possibili interferenze fra programmi contemporaneamente in esecuzione) introdotti dalla multiprogrammazione? |
(3) | Definire in poche parole un sistema operativo time-sharing. In quale situazione può risultare più conveniente utilizzare un sistema time-sharing anzichè un personal computer o una workstation completamente a disposizione dell'utente ? |
(4) | Un sistema operativo ben progettato deve garantire che un programma non possa inavvertitamente (o volontariamente) compromettere il funzionamento degli altri programmi nel sistema. Descrivere quale tipo di supporto hardware può supportare la protezione della CPU (un processo non deve poter occupare indefinitamente la CPU), la protezione della memoria (un processo non deve poter accedere e tanto meno modificare i dati e/o il codice di un altro processo), la protezione dei dispositivi di I/O (un processo non deve poter eseguire operazioni illegali di I/O, per esempio andare a scrivere su settori del disco dove sono contenute informazioni cruciali per la gestione del file system o dati di altri utenti). |
(5) | Spiegare la differenza fra interrupt e trap (fare alcuni esempi concreti di eventi che causano interrupt e di eventi che causano trap). Cosa succede quando si verifica un interrupt o una trap? |
(6) | Elencare le principali componenti di un sistema operativo ed elencare per ciascuna di esse le principali funzioni svolte. |
(7) | Cos'è una system call? |
(8) | Descrivere alcuni modi alternativi di strutturare un sistema operativo discutendo pregi e difetti di ciascun approccio. |
(1) | Cos'è un processo? Quali sono i possibili stati in cui si può trovare un processo e quali sono gli eventi che causano il passaggio da uno stato all'altro? (illustrare le possibili transizioni di stato attraverso un diagramma degli stati). |
(2) | Che cos'è il process control block (PCB)? Elencare quali informazioni sono contenute nel PCB. |
(3) | Che cos'è il context switch? Quale componente del sistema operativo decide quale processo diventerà running al momento del context switch? Quale componente del sistema operativo effettua le operazioni necessarie per realizzare il context switch? |
(4) | Che differenza c'è fra un processo e un thread? |
(1) | Fare un esempio di situazione di corsa critica (race condition). I problemi di corsa critica si manifestano sempre ad ogni esecuzione concorrente dei processi coinvolti? |
(2) |
Generalizzare l'algoritmo di Peterson (Fig. 2-8 del libro di testo)
al caso di n>2 processi. Suggerimento: Si puo` realizzare simulando il metodo usato per servire i clienti in un negozio solitamente affollato, cioè chi vuole essere servito preleva un numero da un distributore (il processo i segnala così di essere intenzionato ad entrare in sezione critica scrivendo il numero prelevato in un vettore number alla posizione i) e il servizio viene quindi accordato in ordine di numero prelevato (entra in sezione critica il processo che scandendo il vettore number non trova nessuno con numero maggiore al suo). |
(3) |
Supponiamo che anzichè disporre della istruzione Test_and_set
una CPU abbia invece una istruzione (atomica) di Swap così
definita:
procedure Swap(var a,b:boolean) var temp: boolean; begin temp:=a; a:=b; b:=temp; endcome si può implementare la mutua esclusione tramite la swap? E` ammesso il busy waiting. (La soluzione è simile a quella che fa uso della test_and_set). |
(4) |
Il problema dei lettori e degli scrittori prevede che m
processi lettori ed n processi scrittori possano richiedere
di accedere a dati condivisi (per esempio contenuti in un data base).
Si permette l'accesso simutaneo da parte di più lettori
mentre l'accesso da parte di uno scrittore deve essere eseguito
in mutua esclusione con qualsiasi altro processo, sia esso lettore o
scrittore.
Si implementi una soluzione al problema dei lettori e scrittori
in un ambiente a memoria condivisa
utilizzando i semafori oppure utilizzando il costrutto monitor.
Attenzione: Ciò che si chiede di realizzare sono quattro procedure: inizio_lettura,fine_lettura, inizio_scrittura,fine_scrittura, supponendo che ogni processo esegua la procedura inizio_operazione prima di procedere ad effettuare l'operazione di lettura/scrittura, ed esegua la procedura fine_operazione dopo aver completato l'operazione. |
(5) |
Se al precedente esercizio aggiungiamo i seguenti requisiti (che
servono ad evitare la starvation dei processi):
|
(6) |
Come è possibile implementare il costrutto monitor
su un sistema che disponga solo delle primitive semaforiche?
Osservazione: La soluzione dipende dall'eventuale vincolo sull'uso della cond.signal. Se tale istruzione può comparire solo come ultima istruzione nelle procedure del monitor la soluzione è più semplice. |
(7) | Come si possono implementare le primitive semaforiche (up/down) tramite un monitor? Si semplifica l'implementazione se ci si limita al caso dei semafori binari anzichè considerare il caso più generale |
(8) | È possibile implementare correttamente la soluzione al problema di sincronizzazione fra un processo produttore ed un consumatore disponendo solo di semafori binari (ovvero semafori che possono solo assumere i valori 0 e 1) ? |
(9) |
I costrutti linguistici fork-join e cobegin-coend
permettono di creare processi: in cosa differiscono? Hanno
la stessa potenza espressiva?
Provare a realizzare con i due costrutti i seguenti grafi di precedenza:
|
(10) | Realizzare un processo buffer di N posizioni (ovvero capace di contenere al più N messaggi) facendo uso di send sincrone e receive bloccanti, ed utilizzando comandi con guardie. |
(1) |
Si consideri il seguente insieme di processi: ad ognuno è associata
la durata del prossimo CPU-burst e la priorità.
PROC CPU-burst PRIOR P1 10 3 P2 1 1 P3 2 3 P4 1 4 P5 5 2Si suppone che i processi siano arrivati tutti al tempo 0 nell'ordine del corrispondente indice. Si illustri attraverso diagrammi di Gantt l'ordine di esecuzione dei processi utilizzando gli algoritmi FCFS, SJF, priorità (numeri piccoli = priorità alta) e Round Robin con quanto di tempo di 1 unità Calcolare in ciascun caso il tempo di turnaround e il tempo di attesa di ogni processo. Quale algoritmo permette di ottenere il minor tempo medio di attesa? |
(2) |
Si consideri il seguente algoritmo di scheduling basato su priorità
dinamiche (ovvero che cambiano nel tempo).
In questo sistema valori numerici più grandi corrispondono a
priorità più alte.
Quando un processo è nella ready queue, la sua priorità
cambia con un tasso x; quando invece è running
la sua priorità cambia con un tasso y.
Quando un processo entra nella ready queue gli viene assegnata
priorità 0. Assegnando opportuni valori ai parametri x ed y
è possibile ottenere diversi algoritmi di scheduling.
Quali algoritmi di scheduling si ottengono nei due casi seguenti?
|
(3) | |
(4) |
(1) | Si consideri un sistema che possiede 4 risorse tutte dello stesso tipo. Supponiamo che siano in esecuzione tre processi che usano tali risorse e che possono al massimo richiedere 2 risorse ciascuno. Dimostrare che i tre processi non possono mai trovarsi in uno stato di deadlock. |
(2) | Si supponga di aver verificato, utilizzando l'algoritmo del banchiere per 2 tipi di risorsa, che un sistema in cui sono attivi tre processi P1, P2, P3 che condividono le risorse di tipo A,B,C e D, si trova in uno stato sicuro sia rispetto alle risorse di tipo A e B, sia rispetto alle risorse di tipo C e D (ovvero, l'algoritmo è stato fatto prima eseguire considerando solo le risorse di tipo A e quelle di tipo B, e poi considerando solo le risorse di tipo C e quelle di tipo D). Si può concludere che il sistema sia in uno stato sicuro rispetto a tutti e quattro i tipi di risorsa? Giustificare la risposta (anche con un esempio). |
(1) |
Supponiamo che il meccanismo hardware di traduzione degli indirizzi preveda la
presenza di un registro base RB e di un registro limite RL, per cui ogni indirizzo logico
viene tradotto secondo il seguente schema: if indirizzo_logico > RL then TRAP else indirizzo_fisico = indirizzo_logico + RB Quale delle seguenti tecniche di gestione della memoria può essere implementata?
|
(2) |
Si consideri un sistema paginato con tabella delle pagine memorizzata in memoria
centrale. Si supponga che lo spazio degli indirizzi virtuali sia di 16 pagine di 512 parole, la
memoria fisica sia di 64 frame, e ogni descrittore di pagina logica nella tabella delle pagine
occupi una parola.
|
(3) |
Si supponga di avere una memoria fisica di dimensione 4096Kbyte, e di utilizzare uno schema
di gestione a partizioni variabili in cui l'unità minima di allocazione della memoria
è di 64 byte (ovvero lo spazio di memoria viene allocato in multipli di 64 byte).
Si considerino le seguenti strutture per mantenere traccia dello spazio libero disponibile:
|
(4) |
Data la seguente stringa di riferimenti alle pagine di un processo 0, 1, 2, 1, 3, 4, 1, 2, 0, 1 Calcolare il numero di page fault, indicando a fronte di ciascun riferimento l'eventuale vittima, utilizzando
|
(5) |
Si consideri la seguente sequenza di riferimenti in memoria nel caso di un programma di
460 parole: 10, 11, 104, 170, 73, 309, 185, 245, 246, 434, 458, 364
|
(6) |
In un sistema che usa uno schema di gestione della memoria a partizioni variabili,
la lista delle partizioni libere contiene, nell'ordine, una partizione da 100K, una da 500K,
una da 200K, una da 300K e una da 600K.
Come verrebbero allocate le seguenti richieste (sottoposte al sistema nell'ordine indicato)
e utilizzando gli algoritmi First fit, Best fit e Worst fit? 212K, 417K, 112K e 426K |
|
Si consideri un sistema che usa la paginazione su richiesta. Sono state rilevate le
seguenti utilizzazioni medie delle risorse del sistema
|
(1) |
In una organizzazione dell'allocazione dei file simile a quella adottata in UNIX vi sono
14 puntatori nel descrittore di file (mantenuto in memoria durante l'accesso al file)
di cui
|
(2) |
|
(3) | Quali sono le tre componenti del tempo di accesso a disco? Quale di questi tempi tende ad essere dominante? È più conveniente effettuare pochi trasferimenti di blocchi di grosse dimensioni oppure molti trasferimenti di blocchi di piccole dimensioni? |
(4) | Cosa è un pathname relativo? E un pathname assoluto ? Cosa è un link ? In una organizzazione a grafo (aciclico) delle directory, per quale motivo può non essere conveniente mantenere le informazioni relative alla dimensione e alla localizzazione del file su disco all'interno della entry corrispondente nella directory? |
(5) |
Dato un disco a testa mobile con 200 tracce (numerate da 0 a 199), con richiesta in corso di
servizio alla traccia 143, ultima richesta precedentemente servita alla traccia 125 e con la seguente
coda di richieste: 140, 37, 12, 95, 180, 57, 12 Indicare la sequenza di spostamenti della testina per una schedulazione SSF (Shortest Seek First), algoritmo dell'ascensore, algoritmo dell'ascensore nella variante circolare |
(1) | Cosa è un dominio? Come vengono rappresentati i diritti di accesso ad un dato oggetto nella matrice dei diritti di accesso? Quali sono i domini in UNIX? Si facciano degli esempi di cambiamento di dominio in UNIX. Si faccia un esempio di comando UNIX che modifica la matrice degli accessi. |
(2) | Si descrivano differenze, vantaggi e svantaggi per la protezione ad access list e a capability list. UNIX usa un tipo di protezione a capability list o ad access list? |